package fem2.mesh_and_topology;

import java.util.ArrayList;

import fem2.Debugger;

/**
 * abstract class for spatial indexer using tree structure (QuadTree, Octree)
 * 
 * @author hbui
 * 
 */
public abstract class SpatialTree {

	protected double size;

	protected SpatialTree[] branches;

	protected SpatialInfo info;

	/**
	 * check if a point lie in the current branch
	 * 
	 * @param p
	 * @return
	 */
	public abstract boolean isInside(double... p);

	/**
	 * subdivide this branch
	 */
	public abstract void subdivide();

	/**
	 * check intersection with the spatial criteria
	 * 
	 * @param criteria
	 * @return
	 */
	public abstract boolean isIntersected(SpatialCriteria criteria);

	/**
	 * insert information to the tree
	 * 
	 * @param info
	 * @return
	 */
	public boolean insert(SpatialInfo info) {
		double[] p = info.getPosition();

		if (isInside(p)) {
			if (this.info == null) {
				this.info = info;
				return true;
			} else {
				if (branches == null) {
					subdivide();
				}
				for (int i = 0; i < branches.length; i++) {
					if (branches[i].insert(info)) {
						return true;
					}
				}
			}
		}

		return false;
	}

	/**
	 * get the information of current branch
	 * 
	 * @return
	 */
	public SpatialInfo getSpatialInfo() {
		return info;
	}

	/**
	 * query a list of branch satisfying criteria
	 * 
	 * @param criteria
	 * @return
	 */
	public ArrayList<SpatialInfo> queryRange(SpatialCriteria criteria) {

		ArrayList<SpatialInfo> pointList = new ArrayList<SpatialInfo>();

		/*
		 * check collision of the quad/oct with the spatial criteria
		 */
		if (!isIntersected(criteria)) {
			return pointList;
		}

		/*
		 * add the info from current branch
		 */
		if (getSpatialInfo() != null) {
			if (criteria.isSatisfied(getSpatialInfo().getPosition())) {
				pointList.add(getSpatialInfo());
			}
		}

		/*
		 * terminate if there are no children (i.e leaf branch)
		 */
		if (branches == null) {
			return pointList;
		}

		/*
		 * add the info from children
		 */
		for (int i = 0; i < branches.length; i++) {
			pointList.addAll(branches[i].queryRange(criteria));
		}

		return pointList;
	}

	/**
	 * print the tree
	 * 
	 * @param level
	 */
	public void Print(int level) {
		Debugger.watch("spatial stree level " + level);
		if (getSpatialInfo() != null) {
			Debugger.watch(getSpatialInfo().toString());
		}
		if (branches != null) {
			for (int i = 0; i < branches.length; i++) {
				branches[i].Print(level + 1);
			}
		}
	}
}
